package codetop.microsoft.T438;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: 18362
 * @Create: 2022-08-16 10:18:37 星期二
 */
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int left = 0, right = 0, valid = 0, needChar = 0;
        int[] window = new int[26], need = new int[26];
        for (char c : p.toCharArray()) {
            if (need[c - 'a'] == 0)
                needChar++;
            need[c - 'a']++;
        }
        while (right < s.length()) {
            char c = s.charAt(right++);
            if (need[c-'a'] > 0) {
                if (window[c-'a']+1 == need[c-'a'])
                    valid++;
                window[c-'a']++;
            }
            while (needChar == valid) {
                if (right - left == p.length()) {
                    res.add(left);
                }
                char d = s.charAt(left++);
                if (need[d-'a'] > 0) {
                    if (window[d-'a'] == need[d-'a'])
                        valid--;
                    window[d-'a']--;
                }
            }
        }
        return res;
    }
}